%%%-------------------------------------------------------------------
%%% File    : p37.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The number 3797 has an interesting property. Being prime itself, 
%%% it is possible to continuously remove digits from left to right, 
%%% and remain prime at each stage: 3797, 797, 97, and 7. Similarly we 
%%% can work from right to left: 3797, 379, 37, and 3.
%%%
%%% Find the sum of the only eleven primes that are both truncatable 
%%% from left to right and right to left.
%%%
%%% NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
%%%
%%%
%%% Created : 29 Dec 2008
%%%-------------------------------------------------------------------
-module(p37).

%% API
-compile(export_all).

%D1,...,Dn the digits of the solutions:
%D1D2D3...Dn -> From Left: D1D2D3...Dn-1, ..., D1D2, D1 - prime
%               From Right: D2D3...Dn, D3...Dn, Dn-1Dn, Dn - prime
%               D1 in [2,3,5,7], the only primes < 10
%               Dn in [3, 7], as every number ending in 2 and 5 is not prime
%               D2, ...Dn-1 in [1, 3, 7, 9], because of the left ones, 
                                                %a prime can't end with an even digit, 5 or 0
%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution() ->
    Start = [2,3,5,7],
    End = [3, 7],
    Middle = [1,3,7,9],
    %precalculating the 2 digit ones
    lists:sum(chains(Start, End, 10, Start, Middle, End, [SD*10+ED||SD<-Start, ED<-End, is_prime(SD*10+ED)])).

chains([], _, _, _, _, _, Acc) ->Acc;
chains(_, [], _, _, _, _, Acc) ->Acc;
%the algorithm reuses the previously generated chains of minus one digits
chains(LeftChains, RightChains, RightPow10, StartDigits, MiddleDigits, EndDigits, Acc) ->
    %first generate all possible left and right chains without the start/end digit at this level (number of digits) 
    %that form primes
    ChainsL = [Chain*10 + MD || Chain <- LeftChains, MD <- MiddleDigits, is_prime(Chain*10 + MD)],
    ChainsR = [Chain + MD*RightPow10 || Chain <- RightChains, MD <- MiddleDigits, is_prime(Chain + MD*RightPow10)],
    %than complete the primes by adding the last/first digit
    PrimesL = sets:from_list([Chain*10 + ED || Chain <- ChainsL, ED <- EndDigits, is_prime(Chain*10 + ED)]),
    PrimesR = sets:from_list([Chain + SD*RightPow10*10 || Chain <- ChainsR, SD <- StartDigits, is_prime(Chain + SD*RightPow10*10)]),
    Intersection = sets:to_list(sets:intersection(PrimesL, PrimesR)),
    %the solutions should be in both sets
    NewAcc = case Intersection of
                 [] -> Acc;
                 _ -> Acc ++ Intersection
             end,
    chains(ChainsL, ChainsR, RightPow10*10, StartDigits, MiddleDigits, EndDigits, NewAcc).
%%====================================================================
%% Internal functions
%%====================================================================
is_prime(X) ->
    X rem 2 =/= 0 andalso is_prime(X, 3, math:sqrt(X)).
is_prime(_, I, Sqrt) when I > Sqrt ->
    true;
is_prime(X, I, Sqrt) ->
    case X rem I  of
        0 ->
            false;
        _ -> is_prime(X, I + 2, Sqrt)
    end.
